import sys

import pygame


def make_bezier(xys):
    # xys should be a sequence of 2-tuples (Bezier control points)
    n = len(xys)
    combinations = pascal_row(n - 1)

    def bezier(ts):
        # This uses the generalized formula for bezier curves
        # http://en.wikipedia.org/wiki/B%C3%A9zier_curve#Generalization
        result = []
        for t in ts:
            tpowers = (t ** i for i in range(n))
            upowers = reversed([(1 - t) ** i for i in range(n)])
            coefs = [c * a * b for c, a, b in zip(combinations, tpowers, upowers)]
            result.append(
                tuple(sum([coef * p for coef, p in zip(coefs, ps)]) for ps in zip(*xys)))
        return result

    return bezier


def pascal_row(n, memo={}):
    # This returns the nth row of Pascal's Triangle
    if n in memo:
        return memo[n]
    result = [1]
    x, numerator = 1, n
    for denominator in range(1, n // 2 + 1):
        # print(numerator,denominator,x)
        x *= numerator
        x /= denominator
        result.append(x)
        numerator -= 1
    if n & 1 == 0:
        # n is even
        result.extend(reversed(result[:-1]))
    else:
        result.extend(reversed(result))
    memo[n] = result
    return result


ts = [t / 100.0 for t in range(101)]

if __name__ == '__main__':
    pygame.init()

    screen = pygame.display.set_mode((600, 600))

    group = pygame.sprite.Group()

    offset = 80

    while True:
        screen.fill((0, 0, 0))
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                sys.exit()
            if event.type == pygame.MOUSEMOTION:
                group.empty()
                mp = pygame.mouse.get_pos()
                xys = [(0, 0), [(mp[0] - 0) / 2 + -offset, (mp[1] - 0) / 2 + offset], pygame.mouse.get_pos()]
                bezier = make_bezier(xys)
                points = bezier(ts)
                for x, y in points:
                    sp = pygame.sprite.Sprite()
                    sp.image = pygame.Surface((10, 10))
                    sp.image.fill((255, 0, 0))
                    sp.rect = sp.image.get_rect()
                    sp.rect.center = [int(x), int(y)]
                    group.add(sp)

        group.update()
        group.draw(screen)
        pygame.display.update()
